#include<string>
using namespace std;

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int S_idx = S.length() - 1;
        int T_idx = T.length() - 1;
        while (S_idx >= 0 && T_idx >= 0) {
            int cnt = 0;
            while (S_idx >= 0) {
                if (S[S_idx] == '#') {
                    ++cnt;
                    --S_idx;
                }
                else if (cnt > 0) {
                    --cnt; 
                    --S_idx;
                }
                else
                    break;
            }
            cnt = 0;
            while (T_idx >= 0) {
                if (T[T_idx] == '#') {
                    ++cnt;
                    --T_idx;
                }
                else if (cnt > 0) {
                    --cnt;
                    --T_idx;
                }
                else
                    break;
            }
            if (S_idx < 0 || T_idx < 0) break;
            if (S[S_idx] != T[T_idx]) return false;
            --S_idx;
            --T_idx;
        }
        return S_idx == T_idx;
    }
};